package medium;

import metastructure.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，
 * 按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 * 示例 1:
 * 输入:[1,2,3,null,5,null,4]
 * 输出:[1,3,4]
 *
 *  示例 2:
 * 输入:[1,null,3]
 * 输出:[1,3]
 *
 *  示例 3:
 * 输入:[]
 * 输出:[]
 *
 *  提示:
 *  二叉树的节点个数的范围是 [0,100]
 *  -100 <= Node.val <= 100
 * 
 *  Related Topics 树 深度优先搜索 广度优先搜索 二叉树
 *  👍 566 👎 0
 */
public class L199_二叉树的右视角 {

    /**
     * 广度优先遍历.
     *
     * 执行耗时:1 ms,击败了83.23% 的Java用户
     * 内存消耗:36.8 MB,击败了89.90% 的Java用户
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; i++){
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                if (i == size - 1) {
                    res.add(node.val);
                }
            }
        }
        return res;
    }

    List<Integer> res = new ArrayList<>();

    /**
     * 深度优先遍历：根->右->左.
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:37.2 MB,击败了15.87% 的Java用户
     */
    public List<Integer> rightSideView2(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode root, int dept){
        if (root == null) return;
        if (res.size() == dept) res.add(root.val);

        dept++;
        dfs(root.right, dept);
        dfs(root.left, dept);
    }
}
